1. Field of the Invention
The present invention relates to an improved method for characterizing, matching, and identifying biologically unique features such as fingerprints and irises. More specifically, it relates to methods for enhancement of digital images, fast directional convolution and fingerprint-oriented ridge thinning, matching and identification of fingerprints.
2. Description of Related Art
As our society is increasingly electronically-connected, automated personal authentication becomes more important than ever. Traditional techniques, such as those using personal identification numbers (PIN) or passwords, will not satisfy demanding security requirements as they are incapable of differentiating between an authorized person and an impostor. In fact, these techniques can only verify the correctness of the PIN input by a person, but not authenticate the true identity of the authorized person.
To overcome this shortcoming in personal authentication, a number of biometric techniques have been investigated. Biometric authentication capitalizes on some unique bodily features or characteristics of a person, such as fingerprint, voice, hand geometry, face, palm, and iris pattern. Among these biometric features, automated fingerprint identification system (AFIS) has provided the most popular and successful solution, mainly due to the uniqueness of fingerprints and the historical legal aspect of fingerprinting for law enforcement.
A robust and efficient AFIS however, comes with many challenges. The AFIS must be able to differentiate two different fingerprints that may be seemingly identical to the untrained eye. The uniqueness of a fingerprint is characterized by the finely embedded details (called minutiae) of the print, and its overall ridge pattern and density. From a legal standpoint, under Singapore's criminal laws, two fingerprints that contain 16 or more reliably matching minutiae are registered as originating from the same finger of the same person. As a result, a successful AFIS must have strong discrimination power, robustness to certain degrees of deformation in the fingerprint, and fast (or even real-time) processing performance.
Typically, AFIS includes features such as fingerprint image pre-enhancement, orientation filtering, ridge thinning, fingerprint registration and weighted matching score computation. The need for fingerprint image pre-enhancement arises because regardless of the acquisition method and device (either from fingerprint cards, or from fingerprint readers such as optical sensors, or more recently, semiconductor sensors) fingerprints are susceptible to various forms of distortion and noise, including blotches caused by the input environment, skin disease (cuts, and peeling skin), and skin condition (either too wet among younger people, or too dry among elder people). As a result, fingerprint image enhancement is needed to suppress noise, improve contrast, and accentuate the predominant orientation information of the fingerprint.
Orientational filters are generally used for image enhancement according to the local directions of fingerprint ridges, which are obtained from the orientation field of the fingerprint image. Prior art for pre-enhancing includes finding an accurate estimation of the orientation field using some advanced but complicated models and employing a global enhancement technique (e.g., M. Kass et al., “Analyzing Oriented Patterns”, Comput. Vis. Graphics Image Process, 37, 362-385, 1987. N. Ratha et al., “Adaptive Flow Orientation Based Feature Extraction in Fingerprint Images”, Pattern Recognition, 28 (11), 1657-1672, 1995. Vizcaya et al., “A Nonlinear Orientation Model for Global Description of Fingerprints”, Pattern Recognition, 29 (7), 1221-1231, 1996.). Nevertheless, these techniques are usually computationally expensive, and hence less suitable for most AFIS solutions that require real-time processing. Another class of pre-enhancement techniques first accentuates the orientation information and then estimates the orientation field. The most famous technique being the NIST's FFT-based method (e.g., G. T. Candela, et al., “PCASYS-A Pattern-Level Classification Automation System For Fingerprints”, National Institute of Standards and Technology, Visual Image Processing Group, Aug. 1995.), and also some other variants of the FFT-based method (e.g., Sherlock et al., “Fingerprint Enhancement by Directional Fourier Filtering, Proc.” IEE Visual Image Signal Processing vol. 141 (2), 87-94, April 1994).
After the pre-enhancement, orientation filtering is also commonly used to further enhance an input fingerprint image. Many filters have been designed for fingerprint image enhancement (e.g. Gorman et al., “An Approach To Fingerprint Filter Design”, Pattern Recognition, Vol. 22 (1), 29-38, 1989; B. M. Mehtre, Fingerprint image analysis for automatic identification, Machine Vision and Applications, 6, 124-139, 1993; Kamei et al., “Image Filter Design For Fingerprint Enhancement”, Proc. International Symposium on Computer Vision, 109-114, 1995; and Maio et al., “Direct Gray-Scale Minutiae Detection In Fingerprints”, IEEE Transactions on PAMI, Vol. 19, No. 1, 27-40, January 1997), adopted a method to filter the image using a class of orientation filters, and then derive the fingerprint minutiae from the gray-scale image directly. Such a method required intensive computations (e.g., Kasaei et al., “Fingerprint Feature Enhancement Using Block-Direction On Reconstructed Images”, TENCON '97. IEEE Region 10 Annual Conference, Speech and Image Technologies for Computing and Telecommunications., Proceedings of IEEE, vol. 1, 303-306, 1997 attempted to avoid the use of a large class of filters.) To do so, the original image is first rotated to a particular direction to perform the orientation filtering, and then rotated back to the original direction. This rotation process introduces loss of accuracy due to the quantization noise of rotating a discrete image, which may subsequently result in the detection of false minutiae.
Regarding ridge thinning, the prior art has consistently shown that the most effective and robust approach for fingerprint feature extraction is probably using binarization. With this approach, the fingerprint ridges are thinned into binary lines of width of only one pixel before the minutiae are extracted. Some prior art avoids binarization by performing the feature extraction process directly on the grayscale image (e.g., Maio et al., “Direct Gray-Scale Minutiae Detection In Fingerprints”, IEEE Transactions on PAMI, Vol. 19, No. 1, 27-40, January 1997). Such an approach, however, has the drawbacks of missing minutiae and inaccurate minutiae position and direction. Further, many powerful thinning algorithms have been developed for Chinese character recognitions but they are generally not applicable for thinning ridges in fingerprint images (e.g. Chen et al., “A Modified Fast Parallel Algorithm For Thinning Digital Patterns”, Pattern Recognition Letters, 7, 99-106, 1988; R. W. Zhou, “A Novel Single-Pass Thinning Algorithm And An Effective Set Of Performance Criteria”, Pattern Recognition Letters, 16, 1267-1275, 1995; and Zhang, “Redundancy Of Parallel Thinning”, Pattern Recognition Letters, Vol. 18, 27-35, 1997).
The conventional art includes many methods of fingerprint registration. Among them, minutia-based methods are the most popular approaches (e.g. Ratha et al., “A Real-Time Matching System For Large Fingerprint Databases”, IEEE Trans. PAMI, 18 (8), 799-813, Aug., 1996). Such methods make use of the positional and orientational information of each minutia (e.g. Ratha et al., “A Real-Time Matching System For Large Fingerprint Databases”, IEEE Trans. PAMI, 18 (8), 799-813, Aug., 1996; Hrechak et al., “Automated Fingerprint Recognition Using Structural Matching”, Pattern Recognition, 23(8), 893-904, 1990; Wahab et al., “Novel Approach To Automated Fingerprint Recognition”, Proc. IEE Visual Image Signal Processing, 145(3), 160-166, 1998; and Chang et al., “Fast Algorithm For Point Pattern Matching: Invariant To Translations, Rotations And Scale Changes”, Pattern Recognition, 30(2) 311-320, 1997), or possibly together with a segment of ridge associated with the minutia (e.g. Jain et al., “An Identity-Authentication System Using Fingerprint”, Proc. IEEE, 85(9), 1365-1388, 1997). Some minutia-based methods implement registration based on only a few minutiae. These methods are usually simple and fast in computation. However, since these methods depend mainly on the local information of a fingerprint, they cannot handle well the influence of fingerprint deformation and may provide an unsatisfied registration.
To overcome this problem, some other methods that exploit the global features of the prints have been developed. A typical example of such methods is to use the generalized Hough transform (Ratha et al., “A Real-Time Matching System For Large Fingerprint Databases”, IEEE Trans. PAMI, 18 (8), 799-813, Aug., 1996) to perform the registration. This approach allows consideration of the contribution of all the detected minutiae in the prints, and is efficient in computation.
In the weighted matching score computation, the matching score is the final numerical figure that determines if the input print belongs to an authorized person by comparing the score against a predetermined security threshold value. Conventionally, the most used formula for matching score computation is given by the ratio of the number of matched minutiae to the product of the numbers of the input and template minutiae. For example, suppose that D minutiae are found to be matching for prints P and Q. A matching score is then determined using the equation       S    =                            D          2                          M          ⁢                                           ⁢          N                      ,where M and N are the number of the detected minutiae of P and Q respectively. This way of computing the matching score is simple and has been accepted as reasonably accurate.
However, such a matching score may be unreliable and inconsistent with respect to a predetermined threshold. There are situations where two non-matching prints can have a relatively high count of matching minutia, as compared with a pair of matching prints. This results in relatively close matching scores, which also means that the discrimination power to separate between matching and non-matching prints can be poor for a chosen security threshold value.
Therefore a demand exists to provide a method or a system for characterizing, matching and identifying fingerprints or other biologically unique features, which improves on the above mentioned problems of AFIS regarding image data pre-enhancement, orientation filtering, ridge thinning, fingerprint registration and weighted matching score computation.